package algorithm

import "log"

type Array struct {
	begin int
	end   int
}

func MergeSort(nums []int) []int {
	if len(nums) >= 2 {
		splitIdx := len(nums) / 2
		numsA := MergeSort(nums[:splitIdx])
		numsB := MergeSort(nums[splitIdx:])
		return mergeImpl(numsA, numsB)
	}
	return nums
}

func mergeImpl(arrayA []int, arrayB []int) []int {
	result := make([]int, len(arrayA)+len(arrayB))
	i := 0
	j := 0
	cnt := 0
	for i < len(arrayA) && j < len(arrayB) {
		if arrayA[i] < arrayB[j] {
			result[cnt] = arrayA[i]
			cnt++
			i++
		} else {
			result[cnt] = arrayB[j]
			cnt++
			j++
		}
	}
	if i < len(arrayA) {
		for ; i < len(arrayA); i++ {
			result[cnt] = arrayA[i]
			cnt++
		}
	}

	if j < len(arrayB) {
		for ; j < len(arrayB); j++ {
			result[cnt] = arrayB[j]
			cnt++
		}
	}
	log.Println(result)
	return result
}
